/*
 * @Author: 缄默
 * @Date: 2021-11-15 22:20:38
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-15 22:51:47
 */

//佛波纳奇数列的三种解法

#include <iostream>
#include <vector>

using namespace std;

//斐波那契数列递归解法
int s1(int n);

//斐波那契数列dp解法
int s2(int n);

//斐波那契数列再次优化矩阵乘法解法
int s3(int n);
vector<vector<int>> muliMatrix(vector<vector<int>>& m1, vector<vector<int>>& m2);
vector<vector<int>> matrixPower(vector<vector<int>>& m, int p);


int main() {
    cout << s1(5) << endl;
    cout << s2(5) << endl;
    cout << s3(5) << endl;
    return 0;
}

int s1(int n){
    if (n < 1) return 0;
    if (n ==2 || n == 1) return 1;
    return s1(n - 1) + s1(n - 2);
}

int s2(int n) {
    if (n < 1) return 0;
    if (n ==2 || n == 1) return 1;
    int res = 1;
    int pre = 1;
    int tmp = 0;
    for (int i = 2; i < n; i++) {
        tmp = res;
        res = pre + res;
        pre = tmp;
    }
    return res;
}

int s3(int n) {
    if (n < 1) return 0;
    if (n ==2 || n == 1) return 1;
    vector<vector<int>> base {{1, 1}, {1, 0}};
    vector<vector<int>> res  = matrixPower(base, n - 2);
    return res[0][0] + res[1][0];

}

vector<vector<int>> matrixPower(vector<vector<int>>& m, int p) {
    vector<vector<int>> res(m.size(), vector<int>(m[0].size()));
    for (int i = 0; i < res.size(); i++) {
        res[i][i] = 1;
    }
    vector<vector<int>> tmp = m;
    for (; p!= 0; p >>= 1) {
        if ((p & 1) != 0) {
            res = muliMatrix(res, tmp);
        }
        tmp = muliMatrix(tmp, tmp);
    }
    return res;
}

vector<vector<int>> muliMatrix(vector<vector<int>>& m1, vector<vector<int>>& m2) {
    vector<vector<int>> res(m1.size(),vector<int>(m2.size()));
    for (int i = 0; i < m1.size(); i++) {
        for (int j = 0; j < m2[0].size(); j++) {
            for (int k = 0; k < m2.size(); k++) {
                res[i][j] += m1[i][k] * m2[k][j];
            }
        }
    }
    return res;
}

